package leetcode.code0650;

public class Solution extends Solution0650 {

	@Override
	public int minSteps(int n) {
		int ans = 0;
		while (n != 1) {
			int num = almostPrime(n);
			ans += num;
			n = n / num;
		}
		return ans;
	}

	public int almostPrime(int n) {
		if (n == 1)
			return n;
		if (n % 2 == 0)
			return 2;
		for (int i = 3; i <= Math.sqrt(n); i += 2) {
			if (n % i == 0)
				return i;
		}
		return n;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		int ans = so.minSteps(9);
		System.out.println(ans);
//		for (int i = 1; i < 1000; i++) {
//			int temp = i;
//			System.out.print(i + " = ");
//			while (temp != 1) {
//				if (temp % 2 != 0) {
//					int num = isPrime(temp);
//					System.out.print(num + " * ");
//					temp = temp / num;
//				} else {
//					temp = temp / 2;
//					System.out.print(" 2 * ");
//				}
//			}
//			System.out.println(" ");
//		}
	}

}
